﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Text;
using Common.Utilities;

namespace PdfLib.TextScraping
{
    /// <summary>
    /// infer column layout information based on grid detection and 
    /// column header position
    /// </summary>
    public class TableColumnDetector
    {
        /// <summary>
        /// match score is avg of colheader pattern match score
        /// next header position must be to the right of the previous col header position
        /// </summary>
        /// <param name="pdfFilePath"></param>
        /// <param name="pageNum"></param>
        /// <param name="colDetector"></param>
        /// <returns></returns>
        public static double DetectTableColumns(
            string pdfFilePath, int pageNum, 
            TableColumnDetectorInstruction colDetector)
        {
            double matchScore = 0.0;
            Dictionary<string, double> headerMatchScores = new Dictionary<string, double>();
            Dictionary<string, RectangleF> headerPos = new Dictionary<string, RectangleF>();
            float lastXPos = 0.0f;
            foreach(string colHeader in colDetector.ColumnHeadersInFile)
            {
                Dictionary<RectangleF, double> headerPosFound = 
                    PdfPatternSearcher.FoundPatterns(
                        pdfFilePath, pageNum, colHeader, false, 
                        colDetector.MatchScoreThreshold);
                if(headerPosFound ==null || headerPosFound.Count==0)
                {
                    matchScore = 0.0;
                    break;
                }
                else
                {
                    float currentXPos = 0f;
                    foreach(RectangleF rect in headerPosFound.Keys)
                    {
                        if (rect.X > lastXPos)
                        {
                            if (headerMatchScores.ContainsKey(colHeader))
                            {
                                double existingScore = headerMatchScores[colHeader];
                                if (headerPosFound[rect] > existingScore)
                                {
                                    headerMatchScores[colHeader] = headerPosFound[rect];
                                    headerPos[colHeader] = rect;
                                    currentXPos = rect.X;
                                }
                            }
                            else
                            {
                                headerMatchScores.Add(colHeader, headerPosFound[rect]);
                                headerPos.Add(colHeader, rect);
                                currentXPos = rect.X;
                            }
                        }
                    }
                    if(currentXPos>lastXPos)
                    {
                        lastXPos = currentXPos;
                    }
                }
            }
            foreach(string colHeader in headerMatchScores.Keys)
            {
                matchScore += headerMatchScores[colHeader];
            }
            matchScore /= headerMatchScores.Count;
            return matchScore;
        }

        /// <summary>
        /// three methods are supported
        /// 1)  sliding windows no grid
        /// 2)  image rectangle border: having grid between columns but is scanned image
        /// 3)  pdf path: have grid and is drawn using pdf API
        /// </summary>
        /// <param name="pdfFilePath"></param>
        /// <param name="pageNum"></param>
        /// <param name="colDetector"></param>
        /// <returns></returns>
        public static Dictionary<string, RectangleF> DetectTableColumnLayouts(
            string pdfFilePath, int pageNum,
            TableColumnDetectorInstruction colDetector)
        {
            switch(colDetector.ColumnLayoutDetectionType)
            {
                case ColumnBorderDetectorType.SlidingWindow:
                    return DetectTableColumnLayoutsUsingSlidingWindows(
                        pdfFilePath, pageNum, colDetector);
                case ColumnBorderDetectorType.PdfImageRectangle:
                    return DetectTableColumnLayoutsUsingImageRectangles(
                        pdfFilePath, pageNum, colDetector);
                case ColumnBorderDetectorType.PdfPathLine:
                    return DetectTableColumnLayoutsUsingPdfDrawingInstructions(
                        pdfFilePath, pageNum, colDetector);
                default:
                    throw new NotImplementedException("This column detection method is not implemented");
            }
        }

        #region sliding window
        /// <summary>
        /// 1)  collect all matched col header rectangles and store them into 
        ///     dictionary rectangle -> col header
        /// 2)  slide from 0 to page height, each step scan 15 * font height and 
        ///     move down 5 * font height before next scan
        /// 3)  if all col header is detected, the current range in y is stored 
        ///     and break out the scan loop
        /// 4)  col header rectangle is used as base bounding box to scan downwards 
        ///     for any overlapping text boxes, the union is returned
        /// 5)  slide window from col header downward for 3 lines and adjust col 
        ///     header rectangles
        /// </summary>
        /// <param name="pdfFilePath"></param>
        /// <param name="pageNum"></param>
        /// <param name="colDetector"></param>
        /// <returns>
        /// a map between col headers and their bounding rectangles 
        /// (only width is determined, height is open)
        /// </returns>
        private static Dictionary<string, RectangleF> DetectTableColumnLayoutsUsingSlidingWindows(
            string pdfFilePath, int pageNum,
            TableColumnDetectorInstruction colDetector)
        {
            Dictionary<string, RectangleF> colHeaderLayouts = new Dictionary<string, RectangleF>();

            // step 1: store matched colheader rectangles
            Dictionary<RectangleF, string> colHeaderFound = new Dictionary<RectangleF, string>();
            List<float> fontSizeInColHeaders = new List<float>();
            foreach (string colHeader in colDetector.ColumnHeadersInFile)
            {
                Dictionary<RectangleF, double> headerPosFound = PdfPatternSearcher.FoundPatterns(
                    pdfFilePath, pageNum, colHeader, false, colDetector.MatchScoreThreshold);
                if (headerPosFound == null || headerPosFound.Count == 0)
                {
                    throw new Exception("Failed to detect column header " + colHeader);
                }
                else
                {
                    foreach (RectangleF rect in headerPosFound.Keys)
                    {
                        colHeaderFound.Add(rect, colHeader);
                        fontSizeInColHeaders.Add(rect.Height);    
                    }
                }
            }
            float avgFontHeight = StatsUtil.GetAverage(fontSizeInColHeaders);
            SizeF pageSize = PdfPropertyReader.GetPageSize(pdfFilePath, pageNum);

            // step 2: slide window to detect col header ranges
            Range<float> colHeaderRange = new Range<float>();
            float currentYPos = 0f;
            while (currentYPos < pageSize.Height)
            {
                float scanToYPos = currentYPos + avgFontHeight * colDetector.ColumnHeaderSlidingWindwSize;
                Range<float> scanRange = new Range<float>();
                scanRange.FromValue = currentYPos;
                scanRange.ToValue = scanToYPos;
                float lastColHeaderPosX = 0f;
                bool failedToFindColHeaderInCurrentRange = false;
                foreach (string colHeader in colDetector.ColumnHeadersInFile)
                {
                    float colHeaderPosX = -1f;
                    foreach (RectangleF rectFound in colHeaderFound.Keys)
                    {
                        if (colHeaderFound[rectFound] == colHeader && rectFound.X > lastColHeaderPosX)
                        {
                            Range<float> rectRangeY = new Range<float>();
                            rectRangeY.FromValue = rectFound.Top;
                            rectRangeY.ToValue = rectFound.Bottom;
                            if (rectRangeY.OverlapWith(scanRange))
                            {
                                if (colHeaderPosX < 0)
                                {
                                    colHeaderPosX = rectFound.X;
                                    if (colHeaderLayouts.ContainsKey(colHeader))
                                    {
                                        colHeaderLayouts[colHeader] = rectFound;
                                    }
                                    else
                                    {
                                        colHeaderLayouts.Add(colHeader, rectFound);
                                    }
                                }
                                else if (rectFound.X < colHeaderPosX)
                                {
                                    colHeaderPosX = rectFound.X;
                                    if (colHeaderLayouts.ContainsKey(colHeader))
                                    {
                                        colHeaderLayouts[colHeader] = rectFound;
                                    }
                                    else
                                    {
                                        colHeaderLayouts.Add(colHeader, rectFound);
                                    }
                                }
                            }
                        }
                    }
                    if (colHeaderPosX > 0)
                    {
                        lastColHeaderPosX = colHeaderPosX;
                    }
                    else
                    {
                        failedToFindColHeaderInCurrentRange = true;
                        break;  // break out for loop and slide window
                    }
                }

                if (failedToFindColHeaderInCurrentRange)
                {
                    currentYPos += avgFontHeight * colDetector.ColumnHeaderSlidingWindowStep;
                }
                else
                {
                    // step 3: store col header range 
                    colHeaderRange = scanRange;
                    break;      // break out sliding window loop
                }
            }
            if(colHeaderLayouts.Count !=colDetector.ColumnHeadersInFile.Count)
                throw new Exception("Did not find all column headers");

            string firstColumnHeader = colDetector.ColumnHeadersInFile[0];
            colHeaderRange.FromValue = colHeaderLayouts[firstColumnHeader].Top;
            colHeaderRange.ToValue = colHeaderLayouts[firstColumnHeader].Bottom;
            Dictionary<string, Range<float>> colHeaderRangesInX = new Dictionary<string, Range<float>>();
            foreach(string colHeader in colHeaderLayouts.Keys)
            {
                RectangleF colHeaderRect = colHeaderLayouts[colHeader];
                if(colHeaderRect.Top < colHeaderRange.FromValue)
                    colHeaderRange.FromValue = colHeaderRect.Top;
                if(colHeaderRect.Bottom >colHeaderRange.ToValue)
                    colHeaderRange.ToValue = colHeaderRect.Bottom;

                Range<float> colHeaderRangeX = new Range<float>();
                colHeaderRangeX.FromValue = colHeaderRect.Left;
                colHeaderRangeX.ToValue = colHeaderRect.Right;
                colHeaderRangesInX.Add(colHeader, colHeaderRangeX);
            }

            // step 4: col header must be in the upper half of page
            // slide 3 lines into table body to merge col header rectangles
            if (colHeaderRange.ToValue < pageSize.Height / 2)
            {
                List<PdfTextToken> txtTokens = PdfTextReader.ReadPageContentAsTokens(pdfFilePath, pageNum);
                List<PdfTextLine> lineTokens = PdfTextReader.CreateLines(txtTokens);
                lineTokens = PdfTextReader.MergeLines(lineTokens, 0.5);
                lineTokens.Sort();

                colHeaderLayouts = AdjustColumnHeaderRectanglesUsingTableRowTextTokens(
                    lineTokens, colHeaderRange, colHeaderRangesInX,
                    colHeaderLayouts, colDetector);
                colHeaderLayouts = AdjustColumnHeaderRectanglesUsingTableRowTextTokens(
                    lineTokens, colHeaderRange, colHeaderRangesInX,
                    colHeaderLayouts, colDetector);
            }

            // step 5: fill gaps between column header rectangles
            for(int i=0;i<colDetector.ColumnHeadersInFile.Count;i++)
            {
                string colHeader = colDetector.ColumnHeadersInFile[i];
                RectangleF colHeaderRect = colHeaderLayouts[colHeader];
                if(i<colDetector.ColumnHeadersInFile.Count -1)
                {
                    string nextColHeader = colDetector.ColumnHeadersInFile[i + 1];
                    RectangleF nextColHeaderRect = colHeaderLayouts[nextColHeader];
                    if(colHeaderRect.Right < nextColHeaderRect.Left)
                    {
                        colHeaderRect.Width = nextColHeaderRect.Left - colHeaderRect.Left;
                        colHeaderLayouts[colHeader] = colHeaderRect;
                    }
                }
            }

            return colHeaderLayouts;
        }
        #endregion

        #region image rectangle detection
        
        private static Dictionary<string,RectangleF> DetectTableColumnLayoutsUsingImageRectangles(
            string pdfFilePath, int pageNum, 
            TableColumnDetectorInstruction colDetectorSettings)
        {
            // step 1: get rectangles from image
            Image pageImg = PdfImageReader.GetPageImage(pdfFilePath, pageNum);
            if(pageImg ==null)
                throw new Exception("Current page do not have embedded image");
            Bitmap bmp=new Bitmap(pageImg);
            SizeF pageSize = PdfPropertyReader.GetPageSize(pdfFilePath, pageNum);
            ImageProcesser imgProc=new ImageProcesser(bmp, pageSize);
            List<Rectangle> imgRects = imgProc.ReadRectangles();

            // step 2: col header layout
            Dictionary<string, RectangleF> colHeaderLayouts =
                TableColumnDetector.DetectTableColumnLayoutsUsingSlidingWindows(
                    pdfFilePath, pageNum, colDetectorSettings);

            List<RectangleF> detectedRects=new List<RectangleF>();
            foreach(Rectangle imgRect in imgRects)
            {
                // remove any rects that's close to page size width
                if (imgRect.Width <= pageSize.Width * 0.7)
                {
                    detectedRects.Add(new RectangleF(imgRect.X, imgRect.Y, imgRect.Width, imgRect.Height));
                }
            }

            return FitRectangles(pageSize, detectedRects, colHeaderLayouts, colDetectorSettings);
        }

        #endregion

        #region pdf path detection
        private static Dictionary<string, RectangleF> DetectTableColumnLayoutsUsingPdfDrawingInstructions(
            string pdfFilePath, int pageNum,
            TableColumnDetectorInstruction colDetectorSettings)
        {
            
            // step 1: get rectangles from image
            List<RectangleF> pathRects = PdfDrawingInstructionReader.GeRectangles(pdfFilePath, pageNum);
            List<RectangleF> pathRectsFilteredByPageSize = new List<RectangleF>();
            SizeF pageSize = PdfPropertyReader.GetPageSize(pdfFilePath, pageNum);
            if (pathRects != null && pathRects.Count > 0)
            {
                foreach (RectangleF pathRect in pathRects)
                {
                    if (pathRect.Width < pageSize.Width * 0.7)
                    {
                        pathRectsFilteredByPageSize.Add(pathRect);
                    }
                }
            }

            // step 2: col header layout
            Dictionary<string, RectangleF> colHeaderLayouts =
                TableColumnDetector.DetectTableColumnLayoutsUsingSlidingWindows(
                    pdfFilePath, pageNum, colDetectorSettings);


            return FitRectangles(pageSize, pathRectsFilteredByPageSize, colHeaderLayouts, colDetectorSettings);
        }
        #endregion

        #region merge column header rectangles from table body text tokens
        /// <summary>
        /// 
        /// </summary>
        /// <param name="lineTokens"></param>
        /// <param name="colHeaderRange"></param>
        /// <param name="colHeaderRangesInX"></param>
        /// <param name="colHeaderLayouts"></param>
        /// <param name="colDetector"></param>
        /// <returns></returns>
        private static Dictionary<string, RectangleF> AdjustColumnHeaderRectanglesUsingTableRowTextTokens(
            List<PdfTextLine> lineTokens, Range<float> colHeaderRange,
            Dictionary<string, Range<float>> colHeaderRangesInX,
            Dictionary<string, RectangleF> colHeaderLayouts,
            TableColumnDetectorInstruction colDetector)
        {
            lineTokens.Sort();
            int scannedTableBodyLineCount = 0;
            for (int i = 0; i < lineTokens.Count; i++)
            {
                if (lineTokens[i].Rect.Y >= colHeaderRange.ToValue)
                {
                    List<PdfTextToken> lineTxtTokens = lineTokens[i].TextTokens;
                    lineTxtTokens.Sort();
                    for (int j = 0; j < lineTxtTokens.Count; j++)
                    {
                        Range<float> bodyTextRangeX = new Range<float>();
                        bodyTextRangeX.FromValue = lineTxtTokens[j].TextRect.Left;
                        bodyTextRangeX.ToValue = lineTxtTokens[j].TextRect.Right;
                        for (int k = 0; k < colDetector.ColumnHeadersInFile.Count; k++)
                        {
                            string colHeader = colDetector.ColumnHeadersInFile[k];
                            Range<float> headerRangeX = colHeaderRangesInX[colHeader];
                            if (bodyTextRangeX.OverlapWith(headerRangeX))
                            {
                                // resolve conflict, do not merge if current text rect overlaps with prev col header
                                bool canMergeRectangle = true;
                                if (k > 0)
                                {
                                    string prevColHeader = colDetector.ColumnHeadersInFile[k - 1];
                                    if (bodyTextRangeX.OverlapWith(colHeaderRangesInX[prevColHeader]))
                                    {
                                        canMergeRectangle = false;
                                    }
                                }
                                if (canMergeRectangle && k < colDetector.ColumnHeadersInFile.Count - 1)
                                {
                                    string nextColHeader = colDetector.ColumnHeadersInFile[k + 1];
                                    if (bodyTextRangeX.OverlapWith(colHeaderRangesInX[nextColHeader]))
                                    {
                                        canMergeRectangle = false;
                                    }
                                }
                                if (canMergeRectangle)
                                {
                                    Range<float> xRange = new Range<float>();
                                    xRange.FromValue =
                                        Math.Min(headerRangeX.FromValue, bodyTextRangeX.FromValue);
                                    xRange.ToValue =
                                        Math.Max(headerRangeX.ToValue, bodyTextRangeX.ToValue);
                                    Range<float> yRange = new Range<float>();
                                    yRange.FromValue =
                                        Math.Min(colHeaderLayouts[colHeader].Y, lineTxtTokens[j].TextRect.Y);
                                    yRange.ToValue =
                                        Math.Max(
                                            colHeaderLayouts[colHeader].Y + colHeaderLayouts[colHeader].Height,
                                            lineTxtTokens[j].TextRect.Y + lineTxtTokens[j].TextRect.Height);
                                    bodyTextRangeX = xRange;
                                    colHeaderRangesInX[colHeader] = xRange;
                                    colHeaderLayouts[colHeader] =
                                        new RectangleF(xRange.FromValue, yRange.FromValue,
                                                       xRange.ToValue - xRange.FromValue,
                                                       colHeaderLayouts[colHeader].Height);
                                }
                            }
                        }
                    }

                    scannedTableBodyLineCount += 1;
                    if (scannedTableBodyLineCount >= colDetector.AdjustColumnHeaderWidthFromTableRowCount)
                        break;
                }
            }
            return colHeaderLayouts;
        }

        #endregion

        #region fit rectangles using col header layout info
        /// <summary>
        /// 1)  filter rectangles that are less than 
        ///     min colheaderrect width
        /// 2)  filter rectangles by limiting them crossing col header region
        /// 3)  order left over rectangles
        /// 4)  when upper rectangle is splitted in lower rectangles, use
        ///     lower rectangles
        /// 5)  when upper rectangles is merged into a lower rectangle, use 
        ///     upper rectangles
        /// 6)  add any missing head and tail rectangles 
        ///     (i.e.) when left most and right most table grid are missing
        /// 7)  when rectangle spans to >1/2 of a second col header rect, split 
        ///     current rectangle by col header rect
        /// </summary>
        /// <param name="pageSize"></param>
        /// <param name="detectedImageRects"></param>
        /// <param name="colHeaderLayouts"></param>
        /// <param name="colDetectorSettings"></param>
        /// <returns></returns>
        private static Dictionary<string,RectangleF> FitRectangles(
            SizeF pageSize,
            List<RectangleF> detectedImageRects, 
            Dictionary<string,RectangleF> colHeaderLayouts, 
            TableColumnDetectorInstruction colDetectorSettings)
        {
            if (detectedImageRects == null || detectedImageRects.Count > 0)
            {
                return colHeaderLayouts;
            }

            Dictionary<string, RectangleF> colLayouts = new Dictionary<string, RectangleF>();

            float minColHeaderWidth = pageSize.Width;
            foreach (string colHeader in colHeaderLayouts.Keys)
            {
                if (colHeaderLayouts[colHeader].Width < minColHeaderWidth)
                    minColHeaderWidth = colHeaderLayouts[colHeader].Width;
            }

            // step 3: filter by min width
            int idx = 0;
            while (idx < detectedImageRects.Count)
            {
                if (detectedImageRects[idx].Width < minColHeaderWidth)
                    detectedImageRects.RemoveAt(idx);
                else
                    idx++;
            }

            // step 4: filter by y range 
            Range<float> colHeaderRange = new Range<float>();
            colHeaderRange.FromValue = -1f;
            colHeaderRange.ToValue = -1f;
            foreach (string colHeader in colHeaderLayouts.Keys)
            {
                if (colHeaderRange.FromValue < 0)
                    colHeaderRange.FromValue = colHeaderLayouts[colHeader].Y;
                else if (colHeaderRange.FromValue > colHeaderLayouts[colHeader].Y)
                    colHeaderRange.FromValue = colHeaderLayouts[colHeader].Y;
                if (colHeaderRange.ToValue < 0)
                    colHeaderRange.ToValue = colHeaderLayouts[colHeader].Y + colHeaderLayouts[colHeader].Height;
                else if (colHeaderRange.ToValue < colHeaderLayouts[colHeader].Y + colHeaderLayouts[colHeader].Height)
                    colHeaderRange.ToValue = colHeaderLayouts[colHeader].Y + colHeaderLayouts[colHeader].Height;
            }
            idx = 0;
            while (idx < detectedImageRects.Count)
            {
                Range<float> imgRectRange = new Range<float>();
                imgRectRange.FromValue = detectedImageRects[idx].Y;
                imgRectRange.ToValue = detectedImageRects[idx].Y + detectedImageRects[idx].Height;
                if (imgRectRange.OverlapWith(colHeaderRange))
                    idx++;
                else
                    detectedImageRects.RemoveAt(idx);
            }

            // step 5. order 
            List<SortableRectangle> sortableRectangles = new List<SortableRectangle>();
            foreach (RectangleF imgRect in detectedImageRects)
            {
                sortableRectangles.Add(new SortableRectangle(imgRect));
            }

            // step 6&7. use lower rects when lower rects are splitted
            // otherwise use upper rects
            sortableRectangles.Sort();
            List<RectangleF> filteredImageRects = new List<RectangleF>();
            foreach (SortableRectangle imgRect in sortableRectangles)
            {
                if (!HaveUpperCells(imgRect, sortableRectangles))
                {
                    if (HaveBottomCells(imgRect, sortableRectangles))
                    {
                        if (ContainTwoOrMoreBottomCells(imgRect, sortableRectangles))
                        {
                            List<RectangleF> bottomCells = GetContainedNonOverlappingBottomCells(imgRect, sortableRectangles);
                            for (int i = 0; i < bottomCells.Count; i++)
                            {
                                RectangleF bottomCell = bottomCells[i];
                                bottomCell.Y = Math.Min( imgRect.Rect.Y, bottomCell.Y);
                                bottomCell.Height =
                                    Math.Max(imgRect.Rect.Y + imgRect.Rect.Height, bottomCell.Y + bottomCell.Height) -
                                    bottomCell.Y;
                                filteredImageRects.Add(bottomCell);
                            }
                        }
                        else
                        {
                            filteredImageRects.Add(imgRect.Rect);
                        }
                    }
                    else
                    {
                        filteredImageRects.Add(imgRect.Rect);
                    }
                }
            }
            sortableRectangles = new List<SortableRectangle>();
            foreach (RectangleF filteredImgRect in filteredImageRects)
            {
                sortableRectangles.Add(new SortableRectangle(filteredImgRect));
            }

            // step 8. add missing head and tail rectangles
            sortableRectangles.Sort();
            string firstColHeader = colDetectorSettings.ColumnHeadersInFile[0];
            RectangleF firstColRect = colHeaderLayouts[firstColHeader];
            string lastColHeader =
                colDetectorSettings.ColumnHeadersInFile[colDetectorSettings.ColumnHeadersInFile.Count - 1];
            RectangleF lastColRect = colHeaderLayouts[lastColHeader];
            bool foundHeaderRect = false;
            bool foundTailRect = false;
            foreach (SortableRectangle imgRect in sortableRectangles)
            {
                if (imgRect.Rect.X < firstColRect.X + firstColRect.Width)
                    foundHeaderRect = true;
                if (imgRect.Rect.X + imgRect.Rect.Width > lastColRect.X)
                    foundTailRect = true;
            }
            if (!foundHeaderRect)
            {
                sortableRectangles.Add(new SortableRectangle(firstColRect));
            }
            if (!foundTailRect)
            {
                sortableRectangles.Add(new SortableRectangle(lastColRect));
            }
            sortableRectangles.Sort();

            // step 9. split when rect spans 2 or more col headers
            for (int i = 0; i < colDetectorSettings.ColumnHeadersInFile.Count; i++)
            {
                string colHeader = colDetectorSettings.ColumnHeadersInFile[i];
                RectangleF colHeaderLayout = colHeaderLayouts[colHeader];
                Range<float> colHeaderXRange = new Range<float>();
                colHeaderXRange.FromValue = colHeaderLayout.X;
                colHeaderXRange.ToValue = colHeaderLayout.X + colHeaderLayout.Width;
                bool foundImgRect = false;
                for (int k = 0; k < sortableRectangles.Count; k++)
                {
                    RectangleF imgRect = sortableRectangles[k].Rect;
                    Range<float> inflatedImageRectRange = new Range<float>();
                    inflatedImageRectRange.FromValue = imgRect.X - minColHeaderWidth / 2;
                    inflatedImageRectRange.ToValue = imgRect.X + imgRect.Width + minColHeaderWidth / 2;
                    if (inflatedImageRectRange.Contains(colHeaderXRange))
                    {
                        foundImgRect = true;
                        imgRect.Y = colHeaderLayout.Y;
                        imgRect.Height = colHeaderLayout.Height;
                        colLayouts.Add(colHeader, imgRect);
                        break;
                    }
                }
                if (!foundImgRect)
                {
                    colLayouts.Add(colHeader, colHeaderLayout);
                }
            }

            return colLayouts;
        }

        private static bool HaveBottomCells(SortableRectangle currentCell, List<SortableRectangle> allCells)
        {
            Range<float> currentRangeX = new Range<float>();
            currentRangeX.FromValue = currentCell.Rect.X;
            currentRangeX.ToValue = currentCell.Rect.X + currentCell.Rect.Width;
            foreach (SortableRectangle cell in allCells)
            {
                if (cell.Rect.Y >= currentCell.Rect.Y + currentCell.Rect.Height)
                {
                    Range<float> rangeX = new Range<float>();
                    rangeX.FromValue = cell.Rect.X;
                    rangeX.ToValue = cell.Rect.X + cell.Rect.Width;
                    if (currentRangeX.OverlapWith(rangeX))
                        return true;
                }
            }
            return false;
        }

        private static bool HaveUpperCells(SortableRectangle currentCell, List<SortableRectangle> allCells)
        {
            Range<float> currentRangeX = new Range<float>();
            currentRangeX.FromValue = currentCell.Rect.X;
            currentRangeX.ToValue = currentCell.Rect.X + currentCell.Rect.Width;
            foreach (SortableRectangle cell in allCells)
            {
                if (cell.Rect.Y + cell.Rect.Height <= currentCell.Rect.Y)
                {
                    Range<float> rangeX = new Range<float>();
                    rangeX.FromValue = cell.Rect.X;
                    rangeX.ToValue = cell.Rect.X + cell.Rect.Width;
                    if (currentRangeX.OverlapWith(rangeX))
                        return true;
                }
            }
            return false;
        }

        private static bool ContainTwoOrMoreBottomCells(SortableRectangle currentCell, List<SortableRectangle> allCells)
        {
            Range<float> currentRangeX = new Range<float>();
            currentRangeX.FromValue = currentCell.Rect.X;
            currentRangeX.ToValue = currentCell.Rect.X + currentCell.Rect.Width;
            int overlapCount = 0;
            foreach (SortableRectangle cell in allCells)
            {
                if (cell.Rect.Y >= currentCell.Rect.Y + currentCell.Rect.Height)
                {
                    Range<float> rangeX = new Range<float>();
                    rangeX.FromValue = cell.Rect.X;
                    rangeX.ToValue = cell.Rect.X + cell.Rect.Width;
                    if (currentRangeX.OverlapWith(rangeX))
                        overlapCount += 1;
                }
            }
            if (overlapCount >= 2)
                return true;
            else
                return false;
        }

        private static List<RectangleF> GetContainedNonOverlappingBottomCells(SortableRectangle currentCell, List<SortableRectangle> allCells)
        {
            Range<float> currentRangeX = new Range<float>();
            currentRangeX.FromValue = currentCell.Rect.X;
            currentRangeX.ToValue = currentCell.Rect.X + currentCell.Rect.Width;
            List<RectangleF> bottomCells = new List<RectangleF>();
            foreach (SortableRectangle cell in allCells)
            {
                if (cell.Rect.Y >= currentCell.Rect.Y + currentCell.Rect.Height)
                {
                    Range<float> rangeX = new Range<float>();
                    rangeX.FromValue = cell.Rect.X;
                    rangeX.ToValue = cell.Rect.X + cell.Rect.Width;
                    if (currentRangeX.Contains(rangeX))
                    {
                        bottomCells.Add(cell.Rect);
                    }
                }
            }

            return bottomCells;
        }
        #endregion
    }
}
